import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author VernHe
 * @date 2021年08月25日 15:50
 */
public class Solution_0406 {
    public static void main(String[] args) {
        for (int[] ints : reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}})) {
            System.out.println(ints[0] + "----" + ints[1]);
        }
    }

    public static int[][] reconstructQueue(int[][] people) {
        Comparator<int[]> comparator = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        };
        Arrays.sort(people, comparator);
        // 根据ki进行排序
        int len = people.length;
        int[][] res = new int[len][2];
        for (int i = 0; i < len; i++) {
            //前面 正好 有 ki 个身高大于或等于 hi 的人。
            if (people[i][1] >= i) {
                // 可以在这个位置
                res[i] = people[i];
            } else {
                // 前面人多了，需要到第下标为people[i][1]的地方
                int position = people[i][1];
                // position及之后的人往后移动一个位置
                for (int j = i; j > position; j--) {
                    res[j] = res[j - 1];
                }
                // 空出的position位置放正确的人
                res[position] = people[i];
            }
        }
        return res;
    }
}
